一、概述
数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据。
可以把数据结构分为逻辑结构和物理结构两大类。
逻辑结构分类：
a.集合结构：集合结构中数据元素除了属于同一个集合外，他们之间没有任何其他的关系。
b.线性结构：线性结构中的数据元素之间存在一对一的关系
c.树形结构：树形结构中的数据元素之间存在一对多的层次关系
d.图形结构：图形结构的数据元素是多对多的关系
物理结构分类
逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构
顺序存储结构：把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的 ，比如我们常用的数组就是顺序存储结构
链式存储结构：是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置
算法
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。研究算法的最终目的就是如何花更少的时间，如何占用更少的内存去完成相同的需求
算法时间复杂度
执行次数=执行时间
用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。
1.用常数1取代运行时间中的所有加法常数；
2.在修改后的运行次数中，只保留高阶项；
3.如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；
| 描述 | 增长的数量级 | 说明 | 举例 |
|---|---|---|---|
| 常数级别 | 1 | 普通语句 | 将两个数字相加 |
| 对数级别 | logN | 二分策略 | 二分查找 |
| 线性级别 | N | 循环 | 找出最大元素 |
| 线性对数级别 | NlogN | 分治思想 | 归并排序 |
| 平方级别 | N^2 | 双层循环 | 检查所有元素 |
| 立方级别 | N^3 | 三层循环 | 检查所有三元组 |
| 指数级别 | 2^N | 穷举查找 | 检查所有子集 |
他们的复杂程度从低到高依次为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)
空间复杂度
标识对内存的占用 分析同时间复杂度。
二叉树
树的定义及特点
树的定义
树是由n（n>=1）个有限节点组成的一个具有层次关系的集合。
树的特点：
每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树。
二叉树概念及特点：
二叉树是一种特殊的树，在树的基础上添加约束条件：每个节点下最多只有两棵子树。它具有特点：
每个节点最多有两颗子树。
左子树和右子树是有顺序的，次序不能颠倒。
即使某节点只有一个子树，也要区分左右子树。
二叉树实现
一个二叉树节点有三个部分，一个是指向左子树的部分，一个是指向右子树的部分，另外一个是数据部分。可以把这个节点抽象成一个节点对象，节点对象有两个节点对象属性和一个数据属性。
一个二叉树有且只有一个根节点，其余的都是根节点的直接或间接子节点。所以可以把二叉树抽象成一个对象，该对象有一个节点类型的数据，用来保存根节点。
以java实体类为例
/**
* 节点类
* @author pkxing
*
*/
public class Node {
// 节点内容
int value;
// 左节点
Node leftChild;
// 右节点
Node rightChild;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return String.valueOf(value);
}
}/**
* 二叉树类
* @author pkxing
*
*/
public class BinaryTree {
// 根节点
private Node root = null;
// 构造方法
// 有参数
public BinaryTree(int value) {
root = new Node(value);
root.leftChild = null;
root.rightChild = null;
}
// 无参数
public BinaryTree(){}
}二叉树操作
二叉排序树的本质就是一颗二叉树,它具有如下特点:
所有左节点的元素值小于其父节点的元素值.
所有右节点的元素值大于其父节点的元素值.
添加节点
// 二叉树类中方法。
/**
* 插入节点
* @param value 节点的值
* @return 插入成功返回true，否则返回false
*/
public boolean add(int value) {
// 定义变量用来标识是否插入成功，默认值表示插入成功
boolean success = true;
// 根据内容创建节点对象
Node node = new Node(value);
// 判断根节点是否为null，如果为null，则将node对象作为根节点对象
if (root == null) { // 没有根节点
// 将node对象作为根节点对象
root = node;
// 设置左右节点为null
root.leftChild = null;
root.rightChild = null;
} else { // 有根据节点
// 定义变量记录当前遍历的节点对象：默认从根节点对象开始遍历
Node current = root;
// 遍历树上的所有节点对象
while (true) {
if (value < current.value) {
// 来到这里说明node对象应该添加到current节点对象的左边
if (current.leftChild == null) {
current.leftChild = node;
break;
}
// 获得current节点的左子节点对象，并赋值给current变量
current = current.leftChild;
} else if (value > current.value) {
// 来到这里说明node对象应该添加到current节点对象的右边
if (current.rightChild == null) {
current.rightChild = node;
break;
}
// 获得current节点的右子节点对象，并赋值给current变量
current = current.rightChild;
} else { // value值已经存在了，则直接返回false
success = false;
break;
}
}
}
// 插入成功
return success;
}查询节点
先查找其根节点，如果根节点的元素值和要查找的元素值相等，则返回该根节点对象。否则，比较根节点的元素和要查找的元素，
如果元素值大于根节点元素值，则查询其右子树。
如果元素值小于根节点元素值，则查询其左子树。
// 二叉树类中添加方法
/**
* 根据节点内容查找节点对象
* @param value 内容
* @return 查找到的节点对象，如果没有则返回null
*/
public Node get(int value) {
// 定义变量记录当前遍历的节点对象，默认从根节点开始遍历
Node current = root;
while (true) {
// 判断value和current节点对象的value是否相同
if (value == current.value) {
// 来到这里则说明current节点对象就是要查找的对象，直接返回即可
return current;
} else if (value < current.value) {
// 来到这里说明要查找的节点对象是在current节点的左子树上
current = current.leftChild;
} else if (value > current.value) {
// 来到这里说明要查找的节点对象是在current节点的右子树上
current = current.rightChild;
}
// 如果current节点对象为null，则说明没有找到对应的节点对象
if (current == null) {
return null;
}
}
}遍历
遍历流程:先遍历左子树，再访问根节点，最后遍历右子树
// 二叉树类中添加方法
/**
* 先遍历左子树，再访问根节点，最后遍历右子树；
*
* @param node
*/
public void inOrder(Node node) {
if (node != null) {
inOrder(node.getLeftChild());
System.out.println(node);
inOrder(node.getRightChild());
}
}
/**
* 将指定节点下的所有子节点的内容按顺序输出
* @param node
*/
public void order2(Node node,List<Integer> list){
if(node == null) return;
// 先遍历node的左节点
order2(node.getLeftChild(),list);
// 将节点内容添加集合中
list.add(node.getValue());
// 遍历node的右节点
order2(node.getRightChild(),list);
}
@Override
public String toString() {
// 创建集合对象
List<Integer> list = new ArrayList<>();
order2(root,list);
return list.toString();
}平衡二叉树
为了避免出现"瘸子"的现象，减少树的高度，提高我们的搜素效率，又存在一种树的结构："平衡二叉树"
它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树的旋转
- 概念：
在构建一棵平衡二叉树的过程中，当有新的结点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。
两种旋转方式:
左旋：
左旋就是将结点的右支往左拉，右子结点变成父结点，并把晋升之后多余的左子结点出让给降级结点的 右子结点；
右旋：
将结点的左支往右拉，左子结点变成了父结点，并把晋升之后多余的右子结点出让给降级结点的左子结 点
四种失衡情况：
左左情况，需要以10为基准结点进行右旋
左右情况，先以7为基准结点进行左旋，再以11为基准结点进行右旋
右左情况，先以15为基准结点进行右旋，再以11为基准结点进行左旋
右右情况，以11未基准结点进行左旋
红黑树
概述：
红黑树是一种自平衡的二叉查找树。
红黑树的每一个结点上都有存储位表示结点的颜色，可以是红或者黑。
红黑树不是高度平衡的，它的平衡是通过"红黑树的特性"进行实现的。
红黑树的特性：
- 每一个结点或是红色的，或者是黑色的；
- 根结点必须是黑色;
- 每个叶结点是黑色的（叶结点是Nil）
- 如果某一个结点是红色，那么它的子结点必须是黑色(不能出现两个红色结点相连的情况)
- 对每一个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点；
图：
